/*-------------------------------------------------------------------------
 *
 * network_gist.c
 *	  网络类型的 GiST 支持。
 *
 * 了解此代码的关键在于定义一组 INET/CIDR 值的
 * "并集"。 它的工作方式如下：
 * 1. 如果值并非全部属于同一 IP 地址族，则 "并集"
 * 是一个伪值，族号为零，minbits 为零，commonbits 为零，
 * 地址全为零。 否则：
 * 2. 并集具有公共的 IP 地址族号码。
 * 3. 并集的 minbits 值是所有输入值中的最小网络掩码长度 ("ip_bits")。
 * 4. 设 C 为所有输入值中共同的前导地址位数 (C 的范围为 0 到 ip_maxbits)。
 * 5. 并集的 commonbits 值是 C。
 * 6. 并集的地址值与其前 C 位的公共前缀相同，
 * 右侧零填充。 地址值的物理宽度是针对地址族的 ip_maxbits。
 *
 * 在叶索引条目（表示单个键）中，commonbits 等于
 * 地址族的 ip_maxbits，minbits 与所表示值的 ip_bits 相同，
 * 地址等于所表示的地址。 虽然看起来我们通过存储
 * 并集格式而非仅仅在叶子键中存储所表示的 INET/CIDR 值
 * 来浪费了一个字节，但由于对齐的考虑，
 * 额外的字节实际上是“免费”的。
 *
 * 请注意，此设计独立跟踪 minbits 和 commonbits；
 * 在任何给定的并集值中，任意一个可能小于另外一个。
 * 这在降树时对我们帮助不大，因为 inet 比较的定义方式：
 * 在非叶节点，我们不能比较超过 minbits 位，即使我们知道它们。
 * 然而，这大大改善了拆分决策的质量。
 * 初步测试表明，搜索的速度比更简单的设计快多达两倍，
 * 在更简单的设计中，单个字段既作为公共前缀长度又作为最小 ip_bits 值。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/utils/adt/network_gist.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <sys/socket.h>

#include "access/gist.h"
#include "access/stratnum.h"
#include "utils/builtins.h"
#include "utils/inet.h"

/*
 * GiST inet_ops 操作类中使用的操作策略编号
 */
#define INETSTRAT_OVERLAPS		RTOverlapStrategyNumber
#define INETSTRAT_EQ			RTEqualStrategyNumber
#define INETSTRAT_NE			RTNotEqualStrategyNumber
#define INETSTRAT_LT			RTLessStrategyNumber
#define INETSTRAT_LE			RTLessEqualStrategyNumber
#define INETSTRAT_GT			RTGreaterStrategyNumber
#define INETSTRAT_GE			RTGreaterEqualStrategyNumber
#define INETSTRAT_SUB			RTSubStrategyNumber
#define INETSTRAT_SUBEQ			RTSubEqualStrategyNumber
#define INETSTRAT_SUP			RTSuperStrategyNumber
#define INETSTRAT_SUPEQ			RTSuperEqualStrategyNumber


/*
 * GiST INET/CIDR 索引键的表示。这个与
 * INET/CIDR 并不完全相同，因为我们需要跟踪共同地址
 * 前缀的长度以及最小子网掩码长度。但只要它
 * 遵循 varlena 头部规则，核心 GiST 代码就不会知道区别。
 * 为简单起见，我们始终使用 1 字节头的 varlena 格式。
 */
typedef struct GistInetKey
{
	uint8		va_header;		/* varlena 头 --- 不要直接触碰 */
	unsigned char family;		/* PGSQL_AF_INET, PGSQL_AF_INET6，或零 */
	unsigned char minbits;		/* 子网掩码中的最小位数 */
	unsigned char commonbits;	/* 地址中共同前缀的位数 */
	unsigned char ipaddr[16];	/* 最多 128 位的共同地址 */
} GistInetKey;

#define DatumGetInetKeyP(X) ((GistInetKey *) DatumGetPointer(X))
#define InetKeyPGetDatum(X) PointerGetDatum(X)

/*
 * 访问宏；并不算太有趣，但我们使用这些来保持与访问 INET/CIDR 值的一致性。注意，family-zero 值是用 4 字节地址存储的，而不是 16。
 */
#define gk_ip_family(gkptr)		((gkptr)->family)
#define gk_ip_minbits(gkptr)	((gkptr)->minbits)
#define gk_ip_commonbits(gkptr) ((gkptr)->commonbits)
#define gk_ip_addr(gkptr)		((gkptr)->ipaddr)
#define ip_family_maxbits(fam)	((fam) == PGSQL_AF_INET6 ? 128 : 32)

/* 这些要求 family 字段已被设置： */
#define gk_ip_addrsize(gkptr) \
	(gk_ip_family(gkptr) == PGSQL_AF_INET6 ? 16 : 4)
#define gk_ip_maxbits(gkptr) \
	ip_family_maxbits(gk_ip_family(gkptr))
#define SET_GK_VARSIZE(dst) \
	SET_VARSIZE_SHORT(dst, offsetof(GistInetKey, ipaddr) + gk_ip_addrsize(dst))


/*
 * GiST 查询一致性检查
 */
Datum inet_gist_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_ent = (GISTENTRY *) PG_GETARG_POINTER(0);
	inet	   *fc_query = PG_GETARG_INET_PP(1);
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid		subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	GistInetKey *fc_key = DatumGetInetKeyP(fc_ent->key);
	int			fc_minbits,
				fc_order;

	/* 此函数提供的所有操作符都是精确的。 */
	*fc_recheck = false;

	/*
	 * 检查 0：不同的家庭
	 *
	 * 如果键表示多个地址家庭，它的子项可能会匹配任何内容。这只能发生在内部索引页面上。
	 */
	if (gk_ip_family(fc_key) == 0)
	{
		Assert(!GIST_LEAF(fc_ent));
		PG_RETURN_BOOL(true);
	}

	/*
	 * 检查 1：不同的家庭
	 *
	 * 匹配的家庭对任何策略都没有帮助。
	 */
	if (gk_ip_family(fc_key) != ip_family(fc_query))
	{
		switch (fc_strategy)
		{
			case INETSTRAT_LT:
			case INETSTRAT_LE:
				if (gk_ip_family(fc_key) < ip_family(fc_query))
					PG_RETURN_BOOL(true);
				break;

			case INETSTRAT_GE:
			case INETSTRAT_GT:
				if (gk_ip_family(fc_key) > ip_family(fc_query))
					PG_RETURN_BOOL(true);
				break;

			case INETSTRAT_NE:
				PG_RETURN_BOOL(true);
		}
		/* 对于所有其他情况，我们可以确保没有匹配 */
		PG_RETURN_BOOL(false);
	}

	/*
	 * 检查 2：网络位计数
	 *
	 * 网络位计数（ip_bits）有助于检查子网络和超网络操作符的叶子。在非叶节点，我们知道每个子项值的 ip_bits >= gk_ip_minbits(key)，因此我们在某些情况下也可以避免下降。
	 */
	switch (fc_strategy)
	{
		case INETSTRAT_SUB:
			if (GIST_LEAF(fc_ent) && gk_ip_minbits(fc_key) <= ip_bits(fc_query))
				PG_RETURN_BOOL(false);
			break;

		case INETSTRAT_SUBEQ:
			if (GIST_LEAF(fc_ent) && gk_ip_minbits(fc_key) < ip_bits(fc_query))
				PG_RETURN_BOOL(false);
			break;

		case INETSTRAT_SUPEQ:
		case INETSTRAT_EQ:
			if (gk_ip_minbits(fc_key) > ip_bits(fc_query))
				PG_RETURN_BOOL(false);
			break;

		case INETSTRAT_SUP:
			if (gk_ip_minbits(fc_key) >= ip_bits(fc_query))
				PG_RETURN_BOOL(false);
			break;
	}

	/*
	 * 检查 3：公共网络位
	 *
	 * 将可用的公共前缀位与查询进行比较，但不要超出查询的网络掩码或表示值中的最小网络掩码。如果这些位与查询不匹配，我们有了答案（并且根据操作符可能需要或不需要下降）。如果它们匹配，并且我们不在叶子节点，我们在所有情况下都会下降。
	 *
	 * 注意，这是仅考虑地址网络部分的操作符的最终检查。
	 */
	fc_minbits = Min(gk_ip_commonbits(fc_key), gk_ip_minbits(fc_key));
	fc_minbits = Min(fc_minbits, ip_bits(fc_query));

	fc_order = bitncmp(gk_ip_addr(fc_key), ip_addr(fc_query), fc_minbits);

	switch (fc_strategy)
	{
		case INETSTRAT_SUB:
		case INETSTRAT_SUBEQ:
		case INETSTRAT_OVERLAPS:
		case INETSTRAT_SUPEQ:
		case INETSTRAT_SUP:
			PG_RETURN_BOOL(fc_order == 0);

		case INETSTRAT_LT:
		case INETSTRAT_LE:
			if (fc_order > 0)
				PG_RETURN_BOOL(false);
			if (fc_order < 0 || !GIST_LEAF(fc_ent))
				PG_RETURN_BOOL(true);
			break;

		case INETSTRAT_EQ:
			if (fc_order != 0)
				PG_RETURN_BOOL(false);
			if (!GIST_LEAF(fc_ent))
				PG_RETURN_BOOL(true);
			break;

		case INETSTRAT_GE:
		case INETSTRAT_GT:
			if (fc_order < 0)
				PG_RETURN_BOOL(false);
			if (fc_order > 0 || !GIST_LEAF(fc_ent))
				PG_RETURN_BOOL(true);
			break;

		case INETSTRAT_NE:
			if (fc_order != 0 || !GIST_LEAF(fc_ent))
				PG_RETURN_BOOL(true);
			break;
	}

	/*
	 * 剩余检查仅适用于叶子和基本比较策略。
	 * 请参阅 network.c 中的 network_cmp_internal() 以获取我们需要匹配的实现。注意，在叶子键中，commonbits 应等于地址长度，因此我们在上面比较了整个网络部分。
	 */
	Assert(GIST_LEAF(fc_ent));

	/*
	 * 检查 4：网络位计数
	 *
	 * 下一步是比较网络掩码宽度。
	 */
	switch (fc_strategy)
	{
		case INETSTRAT_LT:
		case INETSTRAT_LE:
			if (gk_ip_minbits(fc_key) < ip_bits(fc_query))
				PG_RETURN_BOOL(true);
			if (gk_ip_minbits(fc_key) > ip_bits(fc_query))
				PG_RETURN_BOOL(false);
			break;

		case INETSTRAT_EQ:
			if (gk_ip_minbits(fc_key) != ip_bits(fc_query))
				PG_RETURN_BOOL(false);
			break;

		case INETSTRAT_GE:
		case INETSTRAT_GT:
			if (gk_ip_minbits(fc_key) > ip_bits(fc_query))
				PG_RETURN_BOOL(true);
			if (gk_ip_minbits(fc_key) < ip_bits(fc_query))
				PG_RETURN_BOOL(false);
			break;

		case INETSTRAT_NE:
			if (gk_ip_minbits(fc_key) != ip_bits(fc_query))
				PG_RETURN_BOOL(true);
			break;
	}

	/*
	 * 检查 5：整个地址
	 *
	 * 网络掩码位计数相同，因此检查所有地址位。
	 */
	fc_order = bitncmp(gk_ip_addr(fc_key), ip_addr(fc_query), gk_ip_maxbits(fc_key));

	switch (fc_strategy)
	{
		case INETSTRAT_LT:
			PG_RETURN_BOOL(fc_order < 0);

		case INETSTRAT_LE:
			PG_RETURN_BOOL(fc_order <= 0);

		case INETSTRAT_EQ:
			PG_RETURN_BOOL(fc_order == 0);

		case INETSTRAT_GE:
			PG_RETURN_BOOL(fc_order >= 0);

		case INETSTRAT_GT:
			PG_RETURN_BOOL(fc_order > 0);

		case INETSTRAT_NE:
			PG_RETURN_BOOL(fc_order != 0);
	}

	elog(ERROR, "unknown strategy for inet GiST");
	PG_RETURN_BOOL(false);		/* 保持编译器安静 */
}

/*
 * 计算一些 GistInetKeys 的并集参数。
 *
 * 检查 GISTENTRY 数组中元素 m..n 的键，计算以下输出参数：
 * *minfamily_p = 最小 IP 地址家庭号码
 * *maxfamily_p = 最大 IP 地址家庭号码
 * *minbits_p = 最小网络掩码宽度
 * *commonbits_p = 地址之间的公共前导位数
 *
 * 如果有多个地址家庭，则将 minbits 和 commonbits 强制为零。
 */
static void fc_calc_inet_union_params(GISTENTRY *fc_ent,
					   int fc_m, int fc_n,
					   int *fc_minfamily_p,
					   int *fc_maxfamily_p,
					   int *fc_minbits_p,
					   int *fc_commonbits_p)
{
	int			fc_minfamily,
				fc_maxfamily,
				fc_minbits,
				fc_commonbits;
	unsigned char *fc_addr;
	GistInetKey *fc_tmp;
	int			fc_i;

	/* 必须至少有一个键。 */
	Assert(fc_m <= fc_n);

	/* 使用第一个键初始化变量。 */
	fc_tmp = DatumGetInetKeyP(fc_ent[fc_m].key);
	fc_minfamily = fc_maxfamily = gk_ip_family(fc_tmp);
	fc_minbits = gk_ip_minbits(fc_tmp);
	fc_commonbits = gk_ip_commonbits(fc_tmp);
	fc_addr = gk_ip_addr(fc_tmp);

	/* 扫描其余键。 */
	for (fc_i = fc_m + 1; fc_i <= fc_n; fc_i++)
	{
		fc_tmp = DatumGetInetKeyP(fc_ent[fc_i].key);

		/* 确定家庭号码的范围 */
		if (fc_minfamily > gk_ip_family(fc_tmp))
			fc_minfamily = gk_ip_family(fc_tmp);
		if (fc_maxfamily < gk_ip_family(fc_tmp))
			fc_maxfamily = gk_ip_family(fc_tmp);

		/* 查找最小 minbits */
		if (fc_minbits > gk_ip_minbits(fc_tmp))
			fc_minbits = gk_ip_minbits(fc_tmp);

		/* 查找公共位的最小数量 */
		if (fc_commonbits > gk_ip_commonbits(fc_tmp))
			fc_commonbits = gk_ip_commonbits(fc_tmp);
		if (fc_commonbits > 0)
			fc_commonbits = bitncommon(fc_addr, gk_ip_addr(fc_tmp), fc_commonbits);
	}

	/* 如果有多个家庭，则强制 minbits/commonbits 为零。 */
	if (fc_minfamily != fc_maxfamily)
		fc_minbits = fc_commonbits = 0;

	*fc_minfamily_p = fc_minfamily;
	*fc_maxfamily_p = fc_maxfamily;
	*fc_minbits_p = fc_minbits;
	*fc_commonbits_p = fc_commonbits;
}

/*
 * 同上，但是要检查的 GISTENTRY 元素是 offsets[] 数组中列出的索引。
 */
static void fc_calc_inet_union_params_indexed(GISTENTRY *fc_ent,
							   OffsetNumber *fc_offsets, int fc_noffsets,
							   int *fc_minfamily_p,
							   int *fc_maxfamily_p,
							   int *fc_minbits_p,
							   int *fc_commonbits_p)
{
	int			fc_minfamily,
				fc_maxfamily,
				fc_minbits,
				fc_commonbits;
	unsigned char *fc_addr;
	GistInetKey *fc_tmp;
	int			fc_i;

	/* 必须至少有一个键。 */
	Assert(fc_noffsets > 0);

	/* 使用第一个键初始化变量。 */
	fc_tmp = DatumGetInetKeyP(fc_ent[fc_offsets[0]].key);
	fc_minfamily = fc_maxfamily = gk_ip_family(fc_tmp);
	fc_minbits = gk_ip_minbits(fc_tmp);
	fc_commonbits = gk_ip_commonbits(fc_tmp);
	fc_addr = gk_ip_addr(fc_tmp);

	/* 扫描其余键。 */
	for (fc_i = 1; fc_i < fc_noffsets; fc_i++)
	{
		fc_tmp = DatumGetInetKeyP(fc_ent[fc_offsets[fc_i]].key);

		/* 确定家庭号码的范围 */
		if (fc_minfamily > gk_ip_family(fc_tmp))
			fc_minfamily = gk_ip_family(fc_tmp);
		if (fc_maxfamily < gk_ip_family(fc_tmp))
			fc_maxfamily = gk_ip_family(fc_tmp);

		/* 查找最小 minbits */
		if (fc_minbits > gk_ip_minbits(fc_tmp))
			fc_minbits = gk_ip_minbits(fc_tmp);

		/* 查找公共位的最小数量 */
		if (fc_commonbits > gk_ip_commonbits(fc_tmp))
			fc_commonbits = gk_ip_commonbits(fc_tmp);
		if (fc_commonbits > 0)
			fc_commonbits = bitncommon(fc_addr, gk_ip_addr(fc_tmp), fc_commonbits);
	}

	/* 如果有多个家庭，则强制 minbits/commonbits 为零。 */
	if (fc_minfamily != fc_maxfamily)
		fc_minbits = fc_commonbits = 0;

	*fc_minfamily_p = fc_minfamily;
	*fc_maxfamily_p = fc_maxfamily;
	*fc_minbits_p = fc_minbits;
	*fc_commonbits_p = fc_commonbits;
}

/*
 * 构建一个表示并集值的 GistInetKey。
 *
 * 输入是要使用的 family/minbits/commonbits 值，加上指向其中一个并集输入的地址字段的指针。（由于我们将只复制公共位，因此哪个都无所谓。）
 */
static GistInetKey *
fc_build_inet_union_key(int fc_family, int fc_minbits, int fc_commonbits,
					 unsigned char *fc_addr)
{
	GistInetKey *fc_result;

	/* 确保任何未使用的位都被置为零。 */
	fc_result = (GistInetKey *) palloc0(sizeof(GistInetKey));

	gk_ip_family(fc_result) = fc_family;
	gk_ip_minbits(fc_result) = fc_minbits;
	gk_ip_commonbits(fc_result) = fc_commonbits;

	/* 克隆地址的适当字节。 */
	if (fc_commonbits > 0)
		memcpy(gk_ip_addr(fc_result), fc_addr, (fc_commonbits + 7) / 8);

	/* 清理最后一个部分字节中的任何不需要的位。 */
	if (fc_commonbits % 8 != 0)
		gk_ip_addr(fc_result)[fc_commonbits / 8] &= ~(0xFF >> (fc_commonbits % 8));

	/* 正确设置 varlena 头。 */
	SET_GK_VARSIZE(fc_result);

	return fc_result;
}


/*
 * GiST 并集函数
 *
 * 请参阅文件开头的注释以了解并集的定义。
 */
Datum inet_gist_union(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_ent = fc_entryvec->vector;
	int			fc_minfamily,
				fc_maxfamily,
				fc_minbits,
				fc_commonbits;
	unsigned char *fc_addr;
	GistInetKey *fc_tmp,
			   *fc_result;

	/* 确定并集的参数。 */
	fc_calc_inet_union_params(fc_ent, 0, fc_entryvec->n - 1,
						   &fc_minfamily, &fc_maxfamily,
						   &fc_minbits, &fc_commonbits);

	/* 如果有多个家庭，发出家庭号码零。 */
	if (fc_minfamily != fc_maxfamily)
		fc_minfamily = 0;

	/* 使用第一个键初始化地址。 */
	fc_tmp = DatumGetInetKeyP(fc_ent[0].key);
	fc_addr = gk_ip_addr(fc_tmp);

	/* 构造并集值。 */
	fc_result = fc_build_inet_union_key(fc_minfamily, fc_minbits, fc_commonbits, fc_addr);

	PG_RETURN_POINTER(fc_result);
}

/*
 * GiST 压缩函数
 *
 * 将一个 inet 值转换为 GistInetKey。
 */
Datum inet_gist_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_retval;

	if (fc_entry->leafkey)
	{
		fc_retval = palloc(sizeof(GISTENTRY));
		if (DatumGetPointer(fc_entry->key) != NULL)
		{
			inet	   *fc_in = DatumGetInetPP(fc_entry->key);
			GistInetKey *fc_r;

			fc_r = (GistInetKey *) palloc0(sizeof(GistInetKey));

			gk_ip_family(fc_r) = ip_family(fc_in);
			gk_ip_minbits(fc_r) = ip_bits(fc_in);
			gk_ip_commonbits(fc_r) = gk_ip_maxbits(fc_r);
			memcpy(gk_ip_addr(fc_r), ip_addr(fc_in), gk_ip_addrsize(fc_r));
			SET_GK_VARSIZE(fc_r);

			gistentryinit(*fc_retval, PointerGetDatum(fc_r),
						  fc_entry->rel, fc_entry->page,
						  fc_entry->offset, false);
		}
		else
		{
			gistentryinit(*fc_retval, (Datum) 0,
						  fc_entry->rel, fc_entry->page,
						  fc_entry->offset, false);
		}
	}
	else
		fc_retval = fc_entry;
	PG_RETURN_POINTER(fc_retval);
}

/*
 * 我们不需要解压函数，因为其他 GiST inet
 * 支持函数与 GistInetKey 表示法一起工作。
 */

/*
 * GiST 获取函数
 *
 * 从 GistInetKey 重新构建原始的 inet 数据。
 */
Datum inet_gist_fetch(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GistInetKey *fc_key = DatumGetInetKeyP(fc_entry->key);
	GISTENTRY  *fc_retval;
	inet	   *fc_dst;

	fc_dst = (inet *) palloc0(sizeof(inet));

	ip_family(fc_dst) = gk_ip_family(fc_key);
	ip_bits(fc_dst) = gk_ip_minbits(fc_key);
	memcpy(ip_addr(fc_dst), gk_ip_addr(fc_key), ip_addrsize(fc_dst));
	SET_INET_VARSIZE(fc_dst);

	fc_retval = palloc(sizeof(GISTENTRY));
	gistentryinit(*fc_retval, InetPGetDatum(fc_dst), fc_entry->rel, fc_entry->page,
				  fc_entry->offset, false);

	PG_RETURN_POINTER(fc_retval);
}

/*
 * GiST 页面分割惩罚函数
 *
 * 如果地址族不匹配，则收取高额惩罚；如果新值会降低并集的最小位数
 * （最小网络掩码宽度），则收取稍微小一些的惩罚。否则，惩罚与
 * 新的公共地址位数的反比。
 */
Datum inet_gist_penalty(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_origent = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_newent = (GISTENTRY *) PG_GETARG_POINTER(1);
	float	   *fc_penalty = (float *) PG_GETARG_POINTER(2);
	GistInetKey *fc_orig = DatumGetInetKeyP(fc_origent->key),
			   *fc_new = DatumGetInetKeyP(fc_newent->key);
	int			fc_commonbits;

	if (gk_ip_family(fc_orig) == gk_ip_family(fc_new))
	{
		if (gk_ip_minbits(fc_orig) <= gk_ip_minbits(fc_new))
		{
			fc_commonbits = bitncommon(gk_ip_addr(fc_orig), gk_ip_addr(fc_new),
									Min(gk_ip_commonbits(fc_orig),
										gk_ip_commonbits(fc_new)));
			if (fc_commonbits > 0)
				*fc_penalty = 1.0f / fc_commonbits;
			else
				*fc_penalty = 2;
		}
		else
			*fc_penalty = 3;
	}
	else
		*fc_penalty = 4;

	PG_RETURN_POINTER(fc_penalty);
}

/*
 * GiST PickSplit 方法
 *
 * 有两种分割方式。第一种是按地址族分割，
 * 如果输入中出现多个地址族。
 *
 * 第二种更常见的方式是按地址分割。为此，
 * 确定所有关键字共享的前导位数，然后在下一个位上进行分割。
 * （我们目前在执行此操作时不考虑网络掩码宽度；我们需要这样做吗？）
 * 如果这种方式没有得到非平凡的分割，则进行 50-50 分割。
 */
Datum inet_gist_picksplit(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	GIST_SPLITVEC *fc_splitvec = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	GISTENTRY  *fc_ent = fc_entryvec->vector;
	int			fc_minfamily,
				fc_maxfamily,
				fc_minbits,
				fc_commonbits;
	unsigned char *fc_addr;
	GistInetKey *fc_tmp,
			   *fc_left_union,
			   *fc_right_union;
	int			fc_maxoff,
				fc_nbytes;
	OffsetNumber fc_i,
			   *fc_left,
			   *fc_right;

	fc_maxoff = fc_entryvec->n - 1;
	fc_nbytes = (fc_maxoff + 1) * sizeof(OffsetNumber);

	fc_left = (OffsetNumber *) palloc(fc_nbytes);
	fc_right = (OffsetNumber *) palloc(fc_nbytes);

	fc_splitvec->spl_left = fc_left;
	fc_splitvec->spl_right = fc_right;

	fc_splitvec->spl_nleft = 0;
	fc_splitvec->spl_nright = 0;

	/* 确定所有输入的并集参数。 */
	fc_calc_inet_union_params(fc_ent, FirstOffsetNumber, fc_maxoff,
						   &fc_minfamily, &fc_maxfamily,
						   &fc_minbits, &fc_commonbits);

	if (fc_minfamily != fc_maxfamily)
	{
		/* 有多个族，因此按族分割。 */
		for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
		{
			/*
			 * 如果有超过 2 个族，除了最大族外，其他都进入
			 * 左侧并集。这只能发生在输入包括一些
			 * IPv4、一些 IPv6 和一些已经多个族的并集时。
			 */
			fc_tmp = DatumGetInetKeyP(fc_ent[fc_i].key);
			if (gk_ip_family(fc_tmp) != fc_maxfamily)
				fc_left[fc_splitvec->spl_nleft++] = fc_i;
			else
				fc_right[fc_splitvec->spl_nright++] = fc_i;
		}
	}
	else
	{
		/*
		 * 在公共位之后的下一个位上进行分割。如果这导致
		 * 平凡的分割，则尝试向右的下一个位位置。重复此过程直到
		 * 成功；或者如果我们用尽了位，进行任意的 50-50 分割。
		 */
		int			fc_maxbits = ip_family_maxbits(fc_minfamily);

		while (fc_commonbits < fc_maxbits)
		{
			/* 使用 commonbits 的第位进行分割。 */
			int			fc_bitbyte = fc_commonbits / 8;
			int			fc_bitmask = 0x80 >> (fc_commonbits % 8);

			fc_splitvec->spl_nleft = fc_splitvec->spl_nright = 0;

			for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
			{
				fc_tmp = DatumGetInetKeyP(fc_ent[fc_i].key);
				fc_addr = gk_ip_addr(fc_tmp);
				if ((fc_addr[fc_bitbyte] & fc_bitmask) == 0)
					fc_left[fc_splitvec->spl_nleft++] = fc_i;
				else
					fc_right[fc_splitvec->spl_nright++] = fc_i;
			}

			if (fc_splitvec->spl_nleft > 0 && fc_splitvec->spl_nright > 0)
				break;			/* 成功 */
			fc_commonbits++;
		}

		if (fc_commonbits >= fc_maxbits)
		{
			/* 失败...进行 50-50 分割。 */
			fc_splitvec->spl_nleft = fc_splitvec->spl_nright = 0;

			for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff / 2; fc_i = OffsetNumberNext(fc_i))
			{
				fc_left[fc_splitvec->spl_nleft++] = fc_i;
			}
			for (; fc_i <= fc_maxoff; fc_i = OffsetNumberNext(fc_i))
			{
				fc_right[fc_splitvec->spl_nright++] = fc_i;
			}
		}
	}

	/*
	 * 从头计算每一侧的并集值。在大多数情况下，我们
	 * 可以用我们已经知道的值来近似并集值，但这
	 * 确保每一侧的 minbits 和 commonbits 设置得尽可能高。
	 */
	fc_calc_inet_union_params_indexed(fc_ent, fc_left, fc_splitvec->spl_nleft,
								   &fc_minfamily, &fc_maxfamily,
								   &fc_minbits, &fc_commonbits);
	if (fc_minfamily != fc_maxfamily)
		fc_minfamily = 0;
	fc_tmp = DatumGetInetKeyP(fc_ent[fc_left[0]].key);
	fc_addr = gk_ip_addr(fc_tmp);
	fc_left_union = fc_build_inet_union_key(fc_minfamily, fc_minbits, fc_commonbits, fc_addr);
	fc_splitvec->spl_ldatum = PointerGetDatum(fc_left_union);

	fc_calc_inet_union_params_indexed(fc_ent, fc_right, fc_splitvec->spl_nright,
								   &fc_minfamily, &fc_maxfamily,
								   &fc_minbits, &fc_commonbits);
	if (fc_minfamily != fc_maxfamily)
		fc_minfamily = 0;
	fc_tmp = DatumGetInetKeyP(fc_ent[fc_right[0]].key);
	fc_addr = gk_ip_addr(fc_tmp);
	fc_right_union = fc_build_inet_union_key(fc_minfamily, fc_minbits, fc_commonbits, fc_addr);
	fc_splitvec->spl_rdatum = PointerGetDatum(fc_right_union);

	PG_RETURN_POINTER(fc_splitvec);
}

/*
 * GiST 相等函数
 */
Datum inet_gist_same(PG_FUNCTION_ARGS)
{
	GistInetKey *fc_left = DatumGetInetKeyP(PG_GETARG_DATUM(0));
	GistInetKey *fc_right = DatumGetInetKeyP(PG_GETARG_DATUM(1));
	bool	   *fc_result = (bool *) PG_GETARG_POINTER(2);

	*fc_result = (gk_ip_family(fc_left) == gk_ip_family(fc_right) &&
			   gk_ip_minbits(fc_left) == gk_ip_minbits(fc_right) &&
			   gk_ip_commonbits(fc_left) == gk_ip_commonbits(fc_right) &&
			   memcmp(gk_ip_addr(fc_left), gk_ip_addr(fc_right),
					  gk_ip_addrsize(fc_left)) == 0);

	PG_RETURN_POINTER(fc_result);
}
